# include <bits/stdc++.h>
# define N 305
using namespace std;
struct edge
{
    int to,next,len,cost;
}e[N*N*2];
int head[N<<1],cnt=1;
void add_edge(int x,int y,int len,int cost)
{
    e[++cnt]={y,head[x],len,cost};
    head[x]=cnt;
    e[++cnt]={x,head[y],0,-cost};
    head[y]=cnt;
}
int n,m,q,S,T;
int dis[N][N];
int d[N<<1],pre[N<<1];
queue<int> Q;
int res[N];
bool inq[N<<1];
bool spfa()
{
    memset(d,0x3f,sizeof d);
    memset(inq,0,sizeof inq);
    d[S]=0;
    Q.push(S);
    inq[S]=1;
    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        for(int i=head[now];i;i=e[i].next)
            if(e[i].len && d[e[i].to]>d[now]+e[i].cost)
            {
                d[e[i].to]=d[now]+e[i].cost;
                pre[e[i].to]=i;
                if(!inq[e[i].to])
                {
                    inq[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        inq[now]=0;
    }
    return d[T]<1e9;
}
int main()
{
    freopen("journey.in","r",stdin);
    freopen("journey.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=n;i++)
        dis[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,len;
        cin>>x>>y>>len;
        dis[x][y]=min(dis[x][y],len);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    S=n*2+1,T=n*2+2;
    for(int i=1;i<=n;i++)
    {
        add_edge(S,i*2-1,1,0);
        add_edge(i*2,T,1,0);
        for(int j=1;j<=n;j++)
            if(j!=i)
                add_edge(i*2-1,j*2,1,dis[i][j]);
    }
    memset(res,0x3f,sizeof res);
    res[0]=0;
    for(int i=1;i<=n;i++)
    {
        if(!spfa())
            break;
        res[i]=res[i-1]+d[T];
        for(int now=T;now;now=e[pre[now]^1].to)
        {
            e[pre[now]].len--;
            e[pre[now]^1].len++;
        }
    }
    while(q--)
    {
        int c;
        cin>>c;
        int ans=1e9;
        for(int i=0;i<=n;i++)
            ans=min(ans,res[i]+(n-i)*c);
        cout<<ans<<'\n';
    }
    return 0;
}